package basic.study.wantOffer.chapter5;

/**
 * @ClassName Problem56
 * @Description 数组中只出现过一次的数字
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/12 19:29
 * @Version 1.0
 */
public class Problem56 {
    public void findNumsApperOnce(int[] arr, int[] num1, int[] num2) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //异或结果
        int resultExclusionOr = 0;
        for (int num: arr) {
            resultExclusionOr ^= num;
        }
        int indexOf1 = 0;
        //找到从右往左第一个异或结果为1的位
        while (((resultExclusionOr&1) == 0) && (indexOf1 < 4 * 8)) {
            resultExclusionOr = resultExclusionOr >> 1;
            indexOf1++;
        }

        num1[0] = 0;
        num2[0] = 0;
        for (int i = 0; i < arr.length; i++) {
            if (IsBit1(arr[i], indexOf1) == 1) {
                num1[0] ^= arr[i];
            } else {
                num2[0] ^= arr[i];
            }
        }
    }

    int IsBit1(int num, int indexOf1) {
        num = num >> indexOf1;
        return (num & 1);
    }

    /**
     * 数组中唯一只出现一次的数字,其他数字重复过3次
     */
    class Problem56_2 {
        public int singleNumber(int[] nums) {
            int ones = 0;
            int twos = 0;
            for (int num: nums) {
                ones = ones ^ num & ~twos;
                twos = twos ^ num & ~ones;
            }
            return ones;
        }
    }
}
